Devices that use TCP (Transmission Control Protocol) for transmitting and receiving data are now commonly employed. TCP is a protocol used under the OSI (Open Systems Interconnection) Reference Model, and is used when data streamed from an upper layer are divided into data segments for transmission from a sender device to a receiver device. TCP ensures reliable streaming of ordered data segments to a receiver device. Specifically, a sender device assigns information for indicating an order of data (hereinafter referred to as “a sequence number”) to each data segment. The sender device sets the sequence number in a data header upon transmission of a data segment, and initializes a timer at the same time. If there is no acknowledgement from the receiver device of receipt of a transmitted data segment within a projected time (Timeout), the time being determined on the basis of an estimated time for transmission of the data segment to its reception and acknowledgement of its receipt (i.e., estimated round trip time of the data segment), the sender device tentatively determines that the data segment has been lost without reaching the receiver device and retransmits the data segment to the receiver device.
At a sender device, when an acknowledgement is received, a number contained in a header of the received acknowledgement indicates which data segment the received acknowledgement corresponds to. When the receiver device transmits an acknowledgement, it sets a sequence number of a data segment which it expects to receive next in the “acknowledgement number” field in the header of the acknowledgement. For instance, when using sequence numbers starting from 500 and followed by 1000, 1500 etc., an acknowledgement number of an acknowledgement to be transmitted to a sender device is set as 1000 once a data segment having a sequence number “500” is received. Upon receiving such an acknowledgment, the sender device determines that a transmitted data segment has been safely received by a receiver device and transmits a subsequent data segment.
It is to be noted that a sender device receives an acknowledgment having an acknowledgment number 1000 where the sender device has not transmitted a data segment having a sequence number 1000, or where, even if the data segment has been transmitted, the segment has not been received by a receiver device. This acknowledgement number remains set at 1000 until a data segment containing a sequence number 1000 is received at the receiver device even where a subsequent data segment having a sequence number 1500 is already received at a receiver device due to a loss of the data segment having a sequence number 1000. Thus, a sequence number of the least recent data segment which is not received by a receiver device is set as an acknowledgement number.
In the data segment transmission method explained above, reliability is ensured by transmitting from a sender device a subsequent data segment only after receipt at the device from a receiver device of an acknowledgement for a previously transmitted data segment. However, while this method ensures data transmission reliability it inhibits efficiency. To improve efficiency, TCP provides a method for transmitting a certain number of data segments according to a number defined by a “window.” A “window” is a number of bytes or a number of data segments that can be transmitted prior to receipt of an acknowledgement. A window size is determined by a sender device such that it does not exceed an available buffer size of a receiver device. When a sender device receives an acknowledgement for a transmitted data segment(s), a window slides by the number of data segments for which an acknowledgement has been received, and a subsequent data segment(s) is transmitted to the extent by which the window has slid. This method is referred to as a “sliding window method”; and by controlling a window size, data flow is controlled.
If data flow is suspended when a sliding window method is being employed, due to, for example, a break in wireless communication or congestion in a system, transmitted data segments may either be lost in the system or need to be stored temporarily in a node in the network until data communication is restored. Especially, deterioration is more likely to happen in a wireless communication environment. Following restoration of data communication any data segments that are temporarily stored in a node in the network are able to reach the receiver device, albeit with some delay.
However, if communication disruption persists for a relatively long time, and a timeout occurs at a sender device for a transmitted data segment, the sender device retransmits a first data segment from among data segments that have thus far been transmitted but not acknowledged. As a result, the receiver device receives both the data segment temporarily stored in the network (hereinafter referred to as “an original data segment”) and the retransmitted data segment. The receiver device then returns an acknowledgement for the original data segment upon its receipt, and also transmits an acknowledgement for the retransmitted data segment upon its receipt, with each of these acknowledgments normally having the same acknowledgment number. This gives rise to a problem that the sender device is unable to determine whether an acknowledgment received pertains to an originally transmitted or to a retransmitted data segment, and consequently reverts to a state where it is determined that the original data segment failed to reach the receiver device. In the following, an example is given to explain in detail why such a determination is performed.
FIG. 9 is an example sequence diagram showing a case where a packet communication is performed between a server device 10′ (a sender device) and a client device 50 (a receiver device). A 4-digit-number appearing to the right of an initial point of each arrow at server device 10′ in the figure is a sequence number of a data segment transmitted from server device 10′; and a 4-digit-number appearing to the left of an initial point of each arrow at receiver device 50 in the figure is an acknowledgement number included in an acknowledgement transmitted from client device 50. It is assumed here that an original sliding window size is three, i.e., three data segments may be sent without receiving an acknowledgement.
In FIG. 9, three data segments (original data segments) S1–S3 are transmitted for a first time from server device 10′, the data segments S1, S2, and S3 having sequence numbers 0, 1000, and 2000, respectively. A timer is set at server device 10′ upon transmission of the data segments.
In the figure, the data segments S1, S2, and S3 are received at client device 50 with a delay due to deterioration in network communication conditions. Client device 50, upon receiving the original data segment S1, transmits to server device 10′ an acknowledgement R1 having acknowledgment number 1000. Likewise, upon receiving original data segment S2, client device 50 transmits an acknowledgement R2 having acknowledgment number 2000, and an acknowledgement R3 having acknowledgment number 3000 upon receiving original data segment S3.
As shown in the figure, server device 10′ does not receive an acknowledgement from receiver device 50 before an elapsed time measured by a timer exceeds a timeout value. As a result, server device 10′ determines that the original data segment S1 has not been received by client device 50 at the time of timeout, and retransmits a data segment having sequence number 0 (retransmitted data segment S′1). One data segment, i.e., retransmitted data segment S′1, is transmitted here because a window size is reduced to a minimum value upon timeout.
Server device 10′ subsequently receives an acknowledgement R1 having an acknowledgement number 1000. Here, server device 10′ is unable to determine on the basis of the acknowledgement number 1000 whether the acknowledgement R1 pertains to original data segment S1 or to retransmitted data segment S′1, for the reason stated above. Therefore, server device 10′ treats acknowledgement R1 as pertaining to retransmitted data segment S′1, and a data segment having sequence number 1000 is therefore retransmitted (retransmitted data segment S′2). Server device 10′ further retransmits a data segment having a subsequent sequence number 2000 (retransmitted data segment S′3) because the window size is increased by one after receiving the acknowledgement R1.
Server device 10′ subsequently receives an acknowledgement R2 having an acknowledgement number 2000, and subsequent original data segments (original data segment S4 and following original data segments) are sequentially transmitted.
In the example, original data segments S2 and S3 are retransmitted (retransmitted data segments S′2 and S′3) even though they have safely been received at client device 50. That is, since data segments S2 and S3 are received by client device 50 at two different times, the retransmission of data segments S2 and S3 results in unnecessary transmission, although this was not determined at the time of the retransmission. Further, as it is clear from FIG. 9, acknowledgements R′2 and R′3 are also transmitted in response to the retransmitted data segments S′2 and S′3. Thus, a total of four data segments have been unnecessarily transmitted.
Such unnecessary transmission of data segments is not performed if it is determined that an acknowledgement received after retransmission of a data segment pertains to an original data segment in a case where a sender device is unable to determine whether the acknowledgement pertains to the original data segment or the retransmitted data segment.
However, when such a determination is made, an acknowledgment for a retransmitted data segment is regarded as an acknowledgement for an original data segment, wherein a window is slid forwards, causing a subsequent original data segment to be transmitted. When such a transmission of an original data segment is repeated, there is a risk of a cumulative increase in the number of data segments that have been transmitted from server device 10′ but that have not reached client device 50.
To avoid such a risk, it is determined by default that an acknowledgement pertains to an original data segment in a case where a sender device is unable to determine whether an acknowledgement pertains to the original data segment or the retransmitted data segment. However, using this determination, a sender device is unable to avoid unnecessary retransmission of a data segment.
To solve this problem, “The Eifel Detection Algorithm for TCP” (Reiner Ludwig, et. al, http://www.watersprings.org/pub/id/draft-ietf-tsvwg-tcp-eifel-alg-04.txt, 24 Jul., 2002) discloses a technique for enabling reliable determination as to whether an acknowledgment pertains to an original data segment or to a retransmitted data segment by using the TCP Time Stamps Option defined in RFC 1323.
Also, in “On Estimating End-To-End Network Path Properties. 2.8 Impact of Bad Timeouts” (Mark Allman, Vern Paxson, ACM SIGCOMM '99, vol.29, no.4, pp 263–274, October 1999), Allman et. al proposes a technique for using statistical information to estimate whether a received acknowledgment pertains to an original data segment or to a retransmitted data segment in packet communication in a wired packet communication network.
In the Allman's proposal, estimation is performed on the basis of ½ of a minimum round trip time as a threshold value, where the minimum round trip time is the smallest value of a plurality of round trip times obtained by measuring a time from which a data segment is transmitted until a time when an acknowledgment for the segment is received while a connection remains alive between a sender device and a receiver device. In the method, if a time which elapses from retransmission of a data segment until a time when a first acknowledgement is received is equal to or longer than (or longer than) the threshold value, the acknowledgement received is regarded as pertaining to the retransmitted data segment; with the elapsed time being less than (or equal to or less than) the threshold value, while the acknowledgment received is regarded as pertaining to the original data segment.
Determination of the threshold time as being a half that of a minimum round trip time is based on the following conditions:
1. Statistically, a probability of an acknowledgement being received for an originally transmitted data segment is about the same during: a period from retransmission until ½ of a minimum round trip time has elapsed; a period from retransmission until ¾ of a minimum round trip time has elapsed; and a period from retransmission until the complete minimum round trip time has elapsed; and
2. Statistically, a probability of receiving an acknowledgement for a retransmitted data segment sharply increases about a time point shortly after. ½ of the minimum round trip time has elapsed since retransmission.
However, when the Eifel Detection Algorithm is used, time stamp information is always appended to an original data segment at a sender device and to an acknowledgement at a receiver device even under good network conditions. This means that the size of both the original data segment and the acknowledgement data segment is increased. The increase in the amount of transmitted data leads to an increase in communication charges where subscribers are charged for communication in proportion to the amount of segments transmitted through a network. Such an undesirable increase in communication charges is likely to become more pronounced where network conditions are good and instances of data retransmission are likely to be small. Clearly, such increases in communication charges are not desirable for either users of receiver devices and sender devices.
It is feasible to include time stamp information in reserved bits of a TCP header used at the time of communication instead of adding the information to a data segment. However, existing communication systems do not support such a method, and consequently, sender and receiver devices would need to be significantly modified to employ such a method.
Further, even when the technique of Allman is used, an optimum result of the determination cannot be obtained in a mobile communication environment where data segment delay is pronounced in a wireless section.